package main

import "fmt"

func main() {
	input := []int{2, 2, 4, 9, 3}
	fmt.Println("input", input)
	//SelectSort(input)
	//BubbleSort(input)
	InsertSort(input)
	fmt.Println("output", input)
}

// Swap 交换数组中的元素
func Swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

// SelectSort 选择排序
func SelectSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	n := len(arr)
	for i := 0; i < n-1; i++ {
		//0到n-1找最小的位置
		minIndex := i
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		Swap(arr, i, minIndex)
	}
}

// BubbleSort 冒泡排序
func BubbleSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	n := len(arr)
	for i := 0; i < n-1; i++ {
		//逐一比较相邻位置并交换
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[i] {
				Swap(arr, i, j)
			}
		}
	}
}

// InsertSort 插入排序
func InsertSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	n := len(arr)
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0 && arr[j] > arr[j+1]; j-- {
			Swap(arr, j, j+1)
		}
	}
}
